package com.likou;

import java.util.LinkedList;
import java.util.Queue;

public class q207 {

    //    BFS
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }

        // 入度数组
        int[] indegree = new int[numCourses];

        for (int[] prerequisite : prerequisites) {
            indegree[prerequisite[0]] += 1;
        }

        int count = 0;

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            count++;
            for (int[] prerequisite : prerequisites) {
                if (prerequisite[1] == poll) {
                    indegree[prerequisite[0]] -= 1;
                    if (indegree[prerequisite[0]] == 0) {
                        queue.offer(prerequisite[0]);
                    }
                }
            }
        }

        if (count != numCourses) {
            return false;
        }

        return true;
    }
}
